package com.zlsy.learning.leetcode.arraycorrelation.array1013;

/**
 * @author zhouliang
 * @date 2020/5/25 14:47
 * 如果能将一个数组切成三份，每一份的元素的和相等，则返回true，否则返回false。
 */
public class CanThreePartsEqualSum {
    /**
     * 因为a段和=b段和=c段和，所以a+b+c/3肯定能被整除，所以a+b+c%3肯定等于0，
     * 首先判断这个数组的元素和模3是否为0
     *
     * @param A 传入数组
     * @return 返回值
     */
    private static boolean canThreePartsEqualSum(int[] A) {
        int sum = 0;
        for (int i : A) {
            sum += i;
        }
        if (sum % 3 != 0) {
            // 总和不是3的倍数，直接返回false
            return false;
        }

        // 使用双指针,从数组两头开始一起找，节约时间
        //刚开始left为最左坐标，当0位不满足的时候，向前移动一位
        int left = 0;
        //刚开始leftSum为数组的最左元素，当left不满足的时候，取下一位元素加上当前和
        int leftSum = A[left];
        //数组的最右下标，同上不过是向后移动一位
        int right = A.length - 1;
        //数组的最右元素，同leftSum
        int rightSum = A[right];

        // 使用left + 1 < right 的原因，防止只能将数组分成两个部分
        // 例如：[1,-1,1,-1]，使用left < right作为判断条件就会出错
        while (left + 1 < right) {
            if (leftSum == sum / 3 && rightSum == sum / 3) {
                // 左右两边都等于 sum/3 ，中间也一定等于
                return true;
            }
            if (leftSum != sum / 3) {
                // left = 0赋予了初值，应该先left++，在leftSum += A[left];
                leftSum += A[++left];
            }
            if (rightSum != sum / 3) {
                // right = A.length - 1 赋予了初值，应该先right--，在rightSum += A[right];
                rightSum += A[--right];
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] A = new int[]{0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1};
        int[] B = new int[]{3, 3, 6, 5, -2, 2, 5, 1, -9, 4};
        boolean b = canThreePartsEqualSum(A);
        System.out.println(b);
    }
}
